package com.leetcode.tree.recursion;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/6/15 21:18
 */
public class IsSubtree_572 {

    // 注意对根节点是特殊处理，而对于左右子树要进行一般化处理，不能够混在一起
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return t == null;
        // 存在性命题，结果为析取
        return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
        // 递归到达边界
        // 必须保证同时为空--结构一致
        if (s == null && t == null) return true;
        // 有任一不为空，或者结点值不相同，都是不可取的
        if (s == null || t == null || s.val != t.val) return false;
        // 为保证结构一致，关系为合取
        return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
    }


}
